home *** CD-ROM | disk | FTP | other *** search
/ Amiga Plus 2004 #11 / Amiga Plus CD - 2004 - No. 11.iso / AmiSoft / Dev / misc / temgen.lha / Temgen / tg-0.11 / hash.c < prev    next >
C/C++ Source or Header  |  2002-12-18  |  3KB  |  141 lines
  1. #include "alloc.h"
  2. #include "hash.h"
  3. #include "list.h"
  4. #include "sysdefs.h"
  5.  
  6. struct hash {
  7.     unsigned size;
  8.     hash_fun *hf;
  9.     hash_compare *hc;
  10.     struct list_head *tab;
  11. };
  12.  
  13. struct hash_item {
  14.     struct list_head list;
  15.     void *data;
  16. };
  17.  
  18. struct hash *new_hash( unsigned size, hash_fun *hf, hash_compare *hc )
  19. {
  20.     int i;
  21.     struct hash *h = (struct hash*)CALLOC( 1, sizeof(*h) );
  22.     if ( h ) {
  23.         h->size = size;
  24.         h->hf = hf;
  25.         h->hc = hc;
  26.         h->tab = (struct list_head*)CALLOC( size, sizeof(h->tab[0]));
  27.         if ( !h->tab ) {
  28.             FREE( h );
  29.             return NULL;
  30.         }
  31.         
  32.         for ( i=0; i<size; i++ )
  33.             INIT_LIST_HEAD( h->tab + i );
  34.     }
  35.     
  36.     return h;
  37. }
  38.  
  39. void free_hash( struct hash *h )
  40. {
  41.     if ( h ) {
  42.         if ( h->tab ) {
  43.             unsigned i;
  44.             for ( i=0; i<h->size; i++ ) 
  45.                 while( h->tab[ i ].next != h->tab+i ) {
  46.                     struct hash_item *it;
  47.                     it = list_entry( h->tab[ i ].next, struct hash_item, list );
  48.                     list_del( h->tab[ i ].next );
  49.                     FREE( it );
  50.                 }
  51.         }
  52.         free( h );
  53.     }
  54. }
  55.  
  56. int h_add( struct hash *h, void *data )
  57. {
  58.     unsigned hv;
  59.     struct list_head *p;
  60.     struct hash_item *it;
  61.     
  62.     if ( !( h && data ) ) return -1;
  63.  
  64.     hv = h->hf( data ) % h->size;
  65.     for ( p=h->tab[ hv ].next; p != h->tab+hv; p = p->next ) {
  66.         it = list_entry( p, struct hash_item, list );
  67.         if ( h->hc( it->data, data ) == 0 ) return 2;
  68.     }
  69.    
  70.     it = (struct hash_item*)MALLOC( sizeof(*it) );
  71.     if ( it ) {
  72.         it->data = data;
  73.         list_add( &it->list, h->tab + hv );
  74.         return 0;
  75.     }
  76.     else return 1;
  77. }
  78.  
  79. int h_del( struct hash *h, const void *data )
  80. {
  81.     unsigned hv;
  82.     struct list_head *p;
  83.     struct hash_item *it;
  84.     
  85.     if ( !( h && data ) ) return -1;
  86.  
  87.     hv = h->hf( data ) % h->size;
  88.     for ( p=h->tab[ hv ].next; p != h->tab+hv; p = p->next ) {
  89.         it = list_entry( p, struct hash_item, list );
  90.         if ( h->hc( it->data, data ) == 0 ) {
  91.             list_del( &it->list );
  92.             FREE( it );
  93.             return 0;
  94.         }
  95.     }
  96.     
  97.     return 1;
  98. }
  99.  
  100. void *h_get( struct hash *h, const void *data )
  101. {
  102.     unsigned hv;
  103.     struct list_head *p;
  104.     struct hash_item *it;
  105.     
  106.     if ( !( h && data ) ) return NULL;
  107.  
  108.     hv = h->hf( data ) % h->size;
  109.     for ( p=h->tab[ hv ].next; p != h->tab+hv; p = p->next ) {
  110.         it = list_entry( p, struct hash_item, list );
  111.         if ( h->hc( it->data, data ) == 0 ) {
  112.             struct hash_item *it;
  113.             it = list_entry( p, struct hash_item, list );
  114.             return it->data;
  115.         }
  116.     }
  117.     
  118.     return NULL;
  119.     
  120. }
  121.  
  122. int h_foreach( struct hash *h, int (*fun)(void*) )
  123. {
  124.     int res;
  125.     unsigned i;
  126.     struct list_head *p;
  127.     struct hash_item *it;
  128.     
  129.     if ( h && !fun ) return -1;
  130.     if ( !h ) return 0;
  131.     
  132.     for ( i=0; i<h->size; i++ ) {
  133.         for ( p=h->tab[ i ].next; p != h->tab+i; p = p->next ) {
  134.             it = list_entry( p, struct hash_item, list );
  135.             if ( (res = fun( it->data )) != 0 ) return res;
  136.         }
  137.     }
  138.     
  139.     return 0;
  140. }
  141.